public class code3 {
//    top 101 判断链表是否为 回文
public boolean isPail (ListNode head) {
    // write code here
    // 对于 回文数 ，也就是说整个链表中的元素时一半一半相同的
    // 也就是说可以将一半的元素存储到 栈 中，之后再将后一半和反过来的前一半元素进行比较即可
    // 先来针对 head 进行分析
    if(head == null) {
        return false;
    }
    if(head.next == null) {
        return true;
    }

    // 尝试获取整个链表的长度
    int len = 0;
    ListNode p = head;
    while(p != null) {
        p = p.next;
        len++;
    }
    p = head;

    // 创建出一个栈
    Stack<Integer> stack = new Stack<>();
    int half = len / 2;
    // 尝试将一半的值存储到栈中
    while(half != 0) {
        stack.push(p.val);
        p = p.next;
        half--;
    }
    // 在比较之前，还需要注意的是，如果为奇数个元素，是需要排除一下最中间值的
    if (len % 2 == 0) {
        while (!stack.isEmpty()) {
            if (p.val != stack.pop()) {
                return false;
            } else {
                p = p.next;
            }
        }
        return true;
    } else {
        // 这里处理的是元素个数为奇数个的情况
        p = p.next;
        while(!stack.isEmpty()){
            if(p.val != stack.pop()){
                return false;
            }else {
                p = p.next;
            }
        }
        return true;
    }
}
}
